//
// Description: 518. 零钱兑换 II
// Created by Loading on 2022/7/10.
//

#include <bits/stdc++.h>

using namespace std;

int change(int amount, vector<int> &coins) {
    // dp[i] 表示总金额为 i 的硬币组合数
    vector<int> dp(amount + 1);
    dp[0] = 1;

    /* 外层枚举硬币，每次加入新的币种，保证不重复 */
    for (auto &x : coins) {
        for (int i = x; i < amount + 1; ++i) {
            dp[i] += dp[i - x];
        }
    }

    return dp[amount];
}

int main() {
    int amount = 5;
    vector<int> coins{1, 2, 5};

    int res = change(amount, coins);

    cout << res << endl;

    return 0;
}
